#include <vector>
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>
#include <unordered_set>

using namespace std;

//class Solution
//{
//unordered_set<int> _seqSet;
//vector<int> _seq;
//
//public:
//    int getHash(vector<int>& seq)
//    {
//        int hashVal = 0;
//        for (int num : seq) {
//            hashVal = (hashVal * 131 + num) % INT_MAX;
//        }
//        return hashVal;
//    }
//
//    bool check(int seqTarget, vector<int>& nums)
//    {
//        int n = nums.size();
//        _seq.clear();
//        for (int i = n - 1; i >= 0; --i) {
//            if (seqTarget & (1 << i)) {
//                _seq.push_back(nums[n - i - 1]);
//            }
//        }
//        for (int i = 1; i < _seq.size(); ++i) {
//            if (_seq[i - 1] < _seq[i]) {
//                return false;
//            }
//        }
//        int hashVal = getHash(_seq);
//        if (_seq.size() >= 2 && _seqSet.find(hashVal) == _seqSet.end())
//        {
//            _seqSet.insert(hashVal);
//            return true;
//        }
//        return false;
//    }
//
//    vector<vector<int>> findSubsequences(vector<int>& nums)
//    {
//        int n = nums.size();
//        vector<vector<int>> res;
//        for (int k = 0; k < pow(2, n); ++k) {
//            if (check(k, nums)) { res.push_back(_seq); }
//        }
//        return res;
//    }
//};

class Solution {
public:
    int longestPrefix(string s)
    {
        int n = s.size();
        long long hashPrefix = 0, hashPostfix = 0;
        long long mul = 1;
        int base = 131, mod = 1E9 + 7, bottom = 96;
        int maxLength = 0;
        for (int k = 1; k < n; ++k)
        {
            // 前缀之后增加字符，更新前缀哈希值
            hashPrefix = (hashPrefix * base + (s[k - 1] - bottom)) % mod;
            // 后缀之前增加自负，更新后缀哈希值
            //hashPostfix = (mul * (s[n - k] - bottom) + hashPostfix) % mod;
            //mul = (mul * base) % mod;
            //if (hashPostfix == hashPrefix) { maxLength = k; }
        }
        //return s.substr(0, maxLength);
	return hashPrefix;
    }
};

int main()
{
   Solution s;
   //vector<int> nums{4, 6, 7,7};
   //s.findSubsequences(nums);
   string str1("aaaa");
   string str2("aaa");
   std::cout << s.longestPrefix(str1) << endl;
   std::cout << s.longestPrefix(str2) << endl;
   return 0;
}
